#include "UDGraph.h"
#include<iostream>
#include<stack>
#include<queue>
using namespace std;

ostream &operator<<(ostream &output, UDGraph &UDG) {
	bool* ptr = UDG.getMatrix();
	int vexnum = UDG.getVexnum();
 	for (int i = 0; i < vexnum * vexnum; ++i) {
		output << ptr[i] << " ";
		if ((i + 1) % vexnum == 0) {
			output << endl;
		}
	}
	return output;
}
istream &operator>>(istream &input, UDGraph &UDG) {
	delete UDG.getMatrix();
	cout << "please input the number of vertex and arc" << endl;
	int vexnum, arcnum;
	do {
		input >> vexnum >> arcnum;
		if (vexnum < 1 || arcnum < 0) {
			cout << "Illegal! please input again" << endl;
		}
		else
			break;
	} while (1);

	UDG.setVexnum(vexnum);
	UDG.setArcnum(arcnum);
	UDG.setGkind(UD);

	bool* ptr = new bool[vexnum*vexnum];
	if (ptr == NULL) {
		perror("Failed to allocate memory!");
		exit(EXIT_FAILURE);
	}
	for (int i = 0; i < vexnum * vexnum; ++i) {
		ptr[i] = false;
	}

	UDG.setPtrtoMatrix(ptr);
	cout << "Please input arcs,like this: 1 2;\nit means that there is an arc between vex 1 and vex 2" << endl;
	int num = arcnum;
	int v1, v2;
	while (num--) {
		cin >> v1 >> v2;
		--v1; --v2;
		if (v1 < 0 || v2 < 0 || v1 >= vexnum || v2 >= vexnum) {
			cout << "illegal! please input again!" << endl;
			++num;
		}
		ptr[v1*vexnum + v2] = true;
		ptr[v2*vexnum + v1] = true;
	}
	return input;
}

UDGraph::UDGraph(int vexnum, int arcnum):m_pMatrix(nullptr){
	this->setVexnum(vexnum);
	this->setArcnum(arcnum);
	this->setGkind(UD);

	bool* ptr = new bool[vexnum*vexnum];
	if (ptr == NULL) {
		perror("Failed to allocate memory!");
		exit(EXIT_FAILURE);
	}
	for (int i = 0; i < vexnum * vexnum; ++i) {
		ptr[i] = false;
	}

	this->setPtrtoMatrix(ptr);
	cout << "Please input arcs,like this: 1 2;\nit means that there is an arc between vex 1 and vex 2" << endl;
	int num = arcnum;
	int v1, v2;
	while (num--) {
		cin >> v1 >> v2;
		--v1; --v2;
		if (v1 < 0 || v2 < 0 || v1 >= vexnum || v2 >= vexnum) {
			cout << "illegal! please input again!" << endl;
			++num;
		}
		ptr[v1*vexnum + v2] = true;
		ptr[v2*vexnum + v1] = true;
	}
}

UDGraph::~UDGraph(){
	delete this->getMatrix();
	this->setPtrtoMatrix(nullptr);
}

Status UDGraph::BFTraverse() {
	int vexnum = this->getVexnum();
	bool *sign = new bool[vexnum];
	if (sign == nullptr) {
		perror("Failed to allocate memory!");
		exit(EXIT_FAILURE);
	}
	for (int i = 0; i < vexnum; ++i)
		sign[i] = true;

	bool *ptr = this->getMatrix();
	queue<int> Queue;
	int n = vexnum;
	while (n > 0) {
		for (int i = 0; i < vexnum; ++i) {
			if (sign[i]) {
				if (Queue.empty()) {
					Queue.push(i);
					sign[i] = false;
					--n;
				}
				while (!Queue.empty()) {
					int temp = Queue.front();
					Queue.pop();
					cout << temp << endl;
					
					for (int i = 0; i < vexnum; ++i){
						if (ptr[temp * vexnum + i] && sign[i]) {
							sign[i] = false;
							--n;
							Queue.push(i);
						}
					}
				}
			}
		}
	}
	return OK;
}

Status UDGraph::DFTraverse() {
	int vexnum = this->getVexnum();
	bool *sign = new bool[vexnum];
	if (sign == nullptr) {
		perror("Failed to allocate memory!");
		exit(EXIT_FAILURE);
	}
	for (int i = 0; i < vexnum; ++i)
		sign[i] = true;

	bool *ptr = this->getMatrix();
	stack<int> Stack;
	int n = vexnum;
	while (n > 0) {
		for (int i = 0; i < vexnum; ++i) {
			if (sign[i]) {
				if (Stack.empty()) {
					Stack.push(i);
					sign[i] = false;
					--n;
				}
				while (!Stack.empty()) {
					int temp = Stack.top();
					Stack.pop();
					cout << temp << endl;
					for (int i = 0; i < vexnum; ++i) {
						if (ptr[temp * vexnum + i] && sign[i]) {
							sign[i] = false;
							--n;
							Stack.push(i);
						}
					}
				}
			}
		}
	}
	return OK;
}

Status UDGraph::setPtrtoMatrix(bool*matrix){
	m_pMatrix = matrix;
	return OK;
}

bool *UDGraph::getMatrix(){
	return m_pMatrix;
}
